import { log } from "console";
import { TreeNode, preorderTraversal } from "../../const";

/**
 * @link https://leetcode.cn/problems/maximum-depth-of-binary-tree/?envType=study-plan-v2&envId=top-interview-150
 */
function maxDepth(root: TreeNode | null): number {
  // BFS
  if (!root) return 0;
  let q = [[root]];
  let ans = 1;
  while (q.length) {
    let tmpList = q.shift();

    let tmp = [];
    while (tmpList?.length) {
      let n = tmpList.shift();
      if (n?.left) tmp.push(n.left);
      if (n?.right) tmp.push(n.right);
    }
    if (tmp.length) {
      q.push(tmp);
      ans += 1;
    }
    console.log([...tmp]);
  }
  console.log(ans);
  return ans;
}

/**
 * @link https://leetcode.cn/problems/same-tree/?envType=study-plan-v2&envId=top-interview-150
 */
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  const pl: (number | undefined)[] = [];
  const ql: (number | undefined)[] = [];
  const preorderTraversal = (
    p: TreeNode | null,
    list: (number | undefined)[]
  ) => {
    list.push(p?.val);
    if (!p?.left && !p?.right) return;
    if (p?.left) {
      preorderTraversal(p.left, list);
    } else {
      list.push(undefined);
    }
    if (p?.right) {
      preorderTraversal(p.right, list);
    } else {
      list.push(undefined);
    }
  };
  preorderTraversal(p, pl);
  preorderTraversal(q, ql);
  console.log(pl, ql);

  if (pl.length !== ql.length) return false;
  for (let i = 0; i < pl.length; i++) {
    if (pl[i] !== ql[i]) {
      return false;
    }
  }

  return true;
}

/**
 * @link https://leetcode.cn/problems/invert-binary-tree/?envType=study-plan-v2&envId=top-interview-150
 */
function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  const invert = (root: TreeNode) => {
    if (root.left) invertTree(root.left);
    if (root.right) invertTree(root.right);
    let n = root.left;
    root.left = root.right;
    root.right = n;
  };
  invert(root);
  return root;
}

/**
 * @link https://leetcode.cn/problems/symmetric-tree/?envType=study-plan-v2&envId=top-interview-150
 */
function isSymmetric(root: TreeNode | null): boolean {
  if (!root) return false;
  if (!root.left && !root.right) {
    return true;
  }
  if (root.left && root.right) {
    return isSameTree(root.left, invertTree(root.right));
  }
  return false;
}

/**
 * @link https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-interview-150
 */

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const myBuildTree = (
    preorder: number[],
    inorder: number[],
    preorder_left: number,
    preorder_right: number,
    inorder_left: number,
    inorder_right: number
  ) => {
    // 递归出口
    if (preorder_left > preorder_right) return null;
    // 确定先序遍历的根节点
    let preorder_root = preorder_left;
    // 确定中序遍历中的根节点
    let inorder_root = index[preorder[preorder_root]];
    let size_left_tree = inorder_root - inorder_left;
    console.log(preorder_left, preorder_right, size_left_tree);

    let root = new TreeNode(preorder[preorder_left]);

    root.left = myBuildTree(
      preorder,
      inorder,
      preorder_left + 1,
      preorder_left + size_left_tree,
      inorder_left,
      inorder_root - 1
    );

    root.right = myBuildTree(
      preorder,
      inorder,
      preorder_left + size_left_tree + 1,
      preorder_right,
      inorder_root + 1,
      inorder_right
    );

    return root;
  };

  // 构造哈希映射快速定位根节点
  let index: number[] = [];
  for (let i = 0; i < inorder.length; i++) {
    index[inorder[i]] = i;
  }
  let ans = myBuildTree(
    preorder,
    inorder,
    0,
    preorder.length - 1,
    0,
    inorder.length - 1
  );

  console.log(ans);

  preorderTraversal(ans);
  return ans;
}

/**
 * @link https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/?envType=study-plan-v2&envId=top-interview-150
 */
function buildTree2(inorder: number[], postorder: number[]): TreeNode | null {
  const myBuildTree = (
    postorder: number[],
    inorder: number[],
    postorder_left: number,
    postorder_right: number,
    inorder_left: number,
    inorder_right: number
  ) => {
    if (postorder_left > postorder_right) return null;
    // 确定根节点在中序遍历中的位置
    let inorder_root = index[postorder[postorder_right]];
    // 计算右子树数量
    let right_size_tree = inorder_right - inorder_root;
    let root = new TreeNode(inorder[inorder_root]);
    root.left = myBuildTree(
      postorder,
      inorder,
      postorder_left,
      postorder_right - right_size_tree - 1,
      inorder_left,
      inorder_root - 1
    );
    root.right = myBuildTree(
      postorder,
      inorder,
      postorder_right - right_size_tree,
      postorder_right - 1,
      inorder_root + 1,
      inorder_right
    );
    return root;
  };
  let index: number[] = [];
  for (let i = 0; i < inorder.length; i++) {
    index[inorder[i]] = i;
  }
  let ans = myBuildTree(
    postorder,
    inorder,
    0,
    postorder.length - 1,
    0,
    inorder.length - 1
  );
  return ans;
}

/**
 * @link https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/?envType=study-plan-v2&envId=top-interview-150
 */
function connect(root: Node | null): Node | null {
  // BFS
  return null;
}

/**
 * @link https://leetcode.cn/problems/path-sum/?envType=study-plan-v2&envId=top-interview-150
 */
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
  // DFS
  const dfs = (node: TreeNode | null, num: number): boolean => {
    if (!node) return false;

    if (!node?.left && !node?.right) {
      console.log(node, num, num + node.val === targetSum);
      return num + node.val === targetSum;
    }
    num += node.val;
    return dfs(node.left, num) || dfs(node.right, num);
  };

  return root ? dfs(root, 0) : false;
}

/**
 * @link https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/?envType=study-plan-v2&envId=top-interview-150
 */
function flatten(root: TreeNode | null): void {
  const preorder = (node: TreeNode | null) => {
    if (!node) return null;
    if (node.val !== root?.val) {
      tmp.left = null;
      tmp.right = new TreeNode(node.val);
      tmp = tmp.right;
    }

    preorder(node.left);
    preorder(node.right);
  };
  let oldTree = JSON.parse(JSON.stringify(root));
  if (!root) return;
  let tmp = root;
  tmp.left = null;
  // tmp.right = new TreeNode(root?.val);
  preorder(oldTree);
  console.log(root);
}

/**
 * @link https://leetcode.cn/problems/sum-root-to-leaf-numbers/?envType=study-plan-v2&envId=top-interview-150
 */
function sumNumbers(root: TreeNode | null): number {
  const dfs = (node: TreeNode | null, num: string) => {
    if (!node) return null;

    num = num + node.val;
    if (!node.left && !node.right) {
      return (ans += Number(num));
    }
    dfs(node.left, num);
    dfs(node.right, num);
  };
  let ans = 0;
  dfs(root, "");
  return ans;
}

/**
 * @link https://leetcode.cn/problems/binary-search-tree-iterator/?envType=study-plan-v2&envId=top-interview-150
 */
class BSTIterator {
  constructor(root: TreeNode | null) {}

  next(): number {
    return 0;
  }

  hasNext(): boolean {
    return false;
  }
}

/**
 * @link https://leetcode.cn/problems/count-complete-tree-nodes/?envType=study-plan-v2&envId=top-interview-150
 */
function countNodes(root: TreeNode | null): number {
  let ans = 0;
  const preorder = (node: TreeNode | null) => {
    if (!node) return null;
    ans += 1;
    preorder(node.left);
    preorder(node.right);
  };
  preorder(root);
  console.log(ans);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=study-plan-v2&envId=top-interview-150
 */
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  let index = new Map<TreeNode, TreeNode[]>();
  const preorder = (node: TreeNode | null) => {
    if (!node) return null;
    if (node.left) {
      let pre = index.get(node) || [];
      index.set(node.left, [node, ...pre]);
    }
    if (node.right) {
      let pre = index.get(node) || [];
      index.set(node.right, [node, ...pre]);
    }
    preorder(node.left);
    preorder(node.right);
  };
  preorder(root);
  console.log(index);

  return null;
}

export default {
  maxDepth,
  isSameTree,
  invertTree,
  isSymmetric,
  buildTree,
  buildTree2,
  connect,
  hasPathSum,
  flatten,
  sumNumbers,
  BSTIterator,
  countNodes,
  lowestCommonAncestor,
};
